package main

import "fmt"

/*
深度优先搜索
深度优先搜索需要优先使用栈
*/

//TreeNode 定义树结构体
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//Pre 前序遍历 先节点 再左子树 再右子树
func (root *TreeNode) Pre() {
	if root == nil {
		return
	}
	s := NewStack()
	s.Push(root)
	for !s.Empty() {
		cur := s.Pop().(*TreeNode)
		fmt.Println(cur.Val)
		//前序遍历的思路是通过栈，将右子树先行压栈，然后左子树压栈
		if cur.Right != nil {
			s.Push(cur.Right)
		}
		if cur.Left != nil {
			s.Push(cur.Left)
		}
	}
}

//Mid 中序遍历 先访问左子树 再访问根节点 最后访问右子树
func (root *TreeNode) Mid() {
	if root == nil {
		return
	}
	s := NewStack()
	cur := root
	for {
		for cur != nil {
			s.Push(cur)
			cur = cur.Left
		}
		if s.Empty() {
			break
		}
		cur = s.Pop().(*TreeNode)
		fmt.Println(cur.Val)
		cur = cur.Right
	}
}

//Post 后序遍历
func (root *TreeNode) Post() {
	if root == nil {
		return
	}

	s := NewStack()
	out := NewStack()
	s.Push(root)

	for !s.Empty() {
		cur := s.Pop().(*TreeNode)
		out.Push(cur)

		if cur.Left != nil {
			s.Push(cur.Left)
		}
		if cur.Right != nil {
			s.Push(cur.Right)
		}
	}
	for !out.Empty() {
		cur := out.Pop().(*TreeNode)
		fmt.Println(cur.Val)
	}
}

func main() {
	A := &TreeNode{Val: 1}
	A.Left = &TreeNode{Val: 2}
	A.Right = &TreeNode{Val: 3}
	A.Left.Left = &TreeNode{Val: 4}
	A.Left.Right = &TreeNode{Val: 5}
	A.Right.Left = &TreeNode{Val: 6}
	A.Pre()
}
